package com.zac.coroutine.algorithm.selectionsort

/**
 * author zac
 * date 2024/10/8
 *
 * 选择排序:
 * 若需将一个数组从小到大排序,将其进行遍历,中找出最小的数,将其放在新数组的第一位,
 * 然后再在剩余的数中找出最小的,将其排在后面一位,以此类推...
 */
class SelectionSort {


    companion object {
        @JvmStatic
        fun main(args: Array<String>) {
            theRealSelectionSort(
                arrayOf(
                    1,
                    8,
                    6,
                    7,
                    9,
                    10,
                    2,
                    4,
                    76,
                    453,
                    5,
                    754,
                    345,
                    456,
                    22,
                    59,
                    32,
                    346,
                    23,
                    6234,
                    53,
                    222,
                    112
                )
            )
        }

        /**
         * 开辟新的地址的写法
         */
        fun test1(arr: Array<Int>) {
            val result = IntArray(arr.size)

            for (i in 0 until arr.size) {
                var min = -1
                for (j in arr.indices) {
                    if (min == -1) {
                        if (i == 0) {
                            min = arr[j]
                        } else
                            if (arr[j] > result[i - 1]) {
                                min = arr[j]
                            }
                    } else if (min > arr[j]) {
                        if (arr[j] > result[i - 1]) {
                            min = arr[j]
                        }
                    }
                }
                result[i] = min
            }



            result.forEach {
                print("${it},")
            }

        }

        /**
         * 不开辟新空间的写法
         * 这个貌似写成了冒泡...
         */
        fun test2(arr: Array<Int>) {

            for (z in arr) {
                for (i in arr.indices) {
                    if (i == 0) continue
                    if (arr[i] < arr[i - 1]) {
                        val temp = arr[i]
                        arr[i] = arr[i - 1]
                        arr[i - 1] = temp
                    }
                }
            }
            arr.forEach {
                print("${it},")
            }

        }

        /**
         * 真正的选择排序!
         */
        fun theRealSelectionSort(arr: Array<Int>) {

            for (i in arr.indices) {
                var min = arr[i]
                var minIndex = i
                for (j in i until arr.size) {
                    if (arr[j] < min) {
                        min = arr[j]
                        minIndex = j
                    }
                }
                val temp = arr[minIndex]
                arr[minIndex] = arr[i]
                arr[i] = temp
            }
            arr.forEach {
                print("$it,")
            }


        }

        /**
         * 不开辟新空间的写法,再节省点时间
         * 这个貌似写成了冒泡...
         */
        fun test3(arr: Array<Int>) {
            var z = arr.size
            for (j in 0 until z) {
                for (i in arr.indices) {
                    if (i == 0) continue
                    if (arr[i] < arr[i - 1]) {
                        val temp = arr[i]
                        arr[i] = arr[i - 1]
                        arr[i - 1] = temp
                    }
                }
                z--
            }

            arr.forEach {
                print("${it},")
            }

        }

    }


}